class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 快速排序
# class Solution(object):
#     def sortList(self, head):
#         """
#         :type head: ListNode
#         :rtype: ListNode
#         """
#         if not head:
#             return None
#
#         def search(node):
#             head_node = node
#             left_head = None
#             left = None
#             right_head = None
#             right = None
#             while node.next:
#                 node = node.next
#                 if node.val > head_node.val:
#                     if not right_head:
#                         right_head = node
#                         right = node
#                     else:
#                         right.next = node
#                         right = node
#                 else:
#                     if not left_head:
#                         left_head = node
#                         left = node
#                     else:
#                         left.next = node
#                         left = node
#             if left:
#                 left.next = None
#                 left_1, left_2 = search(left_head)
#                 left_2.next = head_node
#                 if right:
#                     right.next = None
#                     right_1, right_2 = search(right_head)
#                     head_node.next = right_1
#                     return left_1, right_2
#                 else:
#                     head_node.next = None
#                     return left_1, head_node
#             else:
#                 if right:
#                     right.next = None
#                     right_1, right_2 = search(right_head)
#                     head_node.next = right_1
#                     return head_node, right_2
#                 else:
#                     head_node.next = None
#                     return head_node, head_node
#
#         return search(head)[0]

# 归并排序,自上而下
# class Solution(object):
#     def sortList(self, head):
#         """
#         :type head: ListNode
#         :rtype: ListNode
#         """
#         node = head
#         right_index = 0
#         while node:
#             right_index += 1
#             node = node.next
#         if right_index == 1:
#             return head
#         mid_index = right_index // 2
#         left_head = head
#         node = head
#         index = 0
#         while index < mid_index - 1:
#             node = node.next
#             index += 1
#         right_head = node.next
#         node.next = None
#         left_head = self.sortList(left_head)
#         right_head = self.sortList(right_head)
#         head = ListNode()
#         node = head
#         while left_head or right_head:
#             if left_head and right_head:
#                 if left_head.val <= right_head.val:
#                     node.next = left_head
#                     node = left_head
#                     left_head = left_head.next
#                 else:
#                     node.next = right_head
#                     node = right_head
#                     right_head = right_head.next
#             else:
#                 if left_head:
#                     node.next = left_head
#                 else:
#                     node.next = right_head
#         return head.next

# 归并排序，自下而上
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        class Solution:
            def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
                def sort_part(p1, p2):
                    head = ListNode(0)
                    node = head
                    while p1 and p2:
                        if p1.val < p2.val:
                            node.next = p1
                            node = node.next
                            p1 = p1.next
                        else:
                            node.next = p2
                            node = node.next
                            p2 = p2.next
                    if not p1:
                        node.next = p2
                    else:
                        node.next = p1
                    while node.next:
                        node = node.next
                    return head.next, node

                count = 0
                node = head
                while node:
                    count += 1
                    node = node.next
                head_node = ListNode(0, head)
                head = head_node.next
                k = 1
                while True:
                    last_node = head_node
                    next_node = head_node.next
                    while next_node:
                        left_head = next_node
                        node = left_head
                        count1 = 1
                        while count1 < k and node.next:
                            node = node.next
                            count1 += 1
                        if node.next:
                            right_head = node.next
                            node.next = None
                            node = right_head
                            count2 = 1
                            while count2 < k and node.next:
                                node = node.next
                                count2 += 1
                            if node.next:
                                next_node = node.next
                                node.next = None
                            else:
                                next_node = None
                            first, last = sort_part(left_head, right_head)
                            last_node.next = first
                            last.next = next_node
                            last_node = last
                        else:
                            break
                    if k >= (count + 1) // 2:
                        break
                    else:
                        k = 2 * k
                return head_node.next






